import { LinkList } from "./LinkList";

export interface SortQueueCompare<T>{
    (t1:T,t2:T):number;
}
// let cb:SortQueueCompare<number>=(n1:number,n2:number)=>{
//     if(n1>n2)
//     {
//         return 1;
//     }
//     else if(n1==n2)
//     {
//         return 0
//     }
//     return -1;
// }

export class SortQueue<T>{
    start:LinkList<T>;
    end:LinkList<T>;
    size:number;
    //比较函数 大于返回1 小于返回-1 等于返回0
    compare:SortQueueCompare<T>;

    constructor(compare:SortQueueCompare<T>)
    {
        this.compare=compare;
        this.size=0;
    }

    isEmpty(){
        return !this.start;
    }

    //入队
    inQueue(item:T):void
    {
        let link:LinkList<T>=new LinkList<T>(item);
        if(!this.end)
        {
            this.end=link;
            this.start=link;
        }
        else{
            let flag=this.compare(this.start.data,link.data)
            if(flag>=0)
            {
                let start=this.start;
                start.pre=link;
                link.next=start;
                link.pre=null;
                this.start=link;
            }
            else{
                let tmp:LinkList<T>=this.end;
                while(tmp)
                {
                    let flag=this.compare(tmp.data,link.data)
                    if(flag<=0)
                    {
                        let next=tmp.next;
                        link.pre=tmp;
                        link.next=next;
                        tmp.next=link;
                        if(next)
                        {
                            next.pre=link;
                        }
                        break;
                    }
                    tmp=tmp.pre;
                }
            }
        }
        this.size++;
    }

    //出队
    dequeen():T{
        //空队列
        if(!this.start)
        {
            return null;
        }
        else{
            let item=this.start;
            let next=item.next;
            if(next)
            {
                next.pre=null;
                this.size--;
                this.start=next;
            }
            else{
                this.start=null
                this.end=null
                this.size=0;
            }
            
            
            
            return item.data;
        }
    }

    //从队列头开始遍历
    getAll(callBack:Function):void{
        let tmp:LinkList<T>=this.start;
        while(tmp)
        {
            callBack(tmp.data)
            tmp=tmp.next;
        }
    }
}
